package com.leetcode;

/**
 * 474. 一和零
 *
 * @author fy
 * @date 2022/3/29 22:17
 */
public class Solution474 {

    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 1; i <= strs.length; i++) {
            String str = strs[i - 1];
            int[] count = getCount(str);
            int zeroCount = count[0];
            int oneCount = count[1];
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= zeroCount && k >= oneCount) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeroCount][k - oneCount] + 1);
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    private int[] getCount(String str) {
        int[] count = new int[2];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c - '0' > 1) {
                continue;
            }
            count[c - '0']++;
        }
        return count;
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"10", "0001", "111001", "1", "0"};
        int m = 5;
        int n = 3;

        int max = new Solution474().findMaxForm(strs, m, n);
        System.out.println(max);
    }

}
